package 中等.双指针;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。
 * 请你找出并返回满足下述全部条件且不重复的四元组 [nums[a],
 * nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，
 * 则认为两个四元组重复）：
 * 0 <= a, b, c, d < n
 * a、b、c 和 d 互不相同
 * nums[a] + nums[b] + nums[c] + nums[d] == target
 * 你可以按 任意顺序 返回答案 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/4sum
 */
public class 四数之和_18 {

    public static void main(String[] args) {

        System.out.println(fourSum(new int[]{2, 2, 2, 2, 2}, 8));

    }

    /**
     * 枚举 a,b + 双指针
     * 注意：枚举 a,b 的时候不能通过 nums[a] == nums[a+1] 来获取
     * nums[a] 不重复的最后一个数，这样会把 b,c,d 也会过滤掉，
     * 可以通过判断 nums[a] == nums[a-1] continue，因为在 nums[a-1]
     * 的位置已经把 nums[a] 可能的情况已经计算到了
     */
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;

        for (int a = 0; a < n - 3; a++) {
            // 跳过重复数字
            if (a > 0 && nums[a] == nums[a - 1]) continue;
            long aNum = nums[a];  // long 避免溢出
            // nums[a] 加上后面3个最小的数都 > target，越往后 target 只会更大
            if (aNum + nums[a + 1] + nums[a + 2] + nums[a + 3] > target) break;
            // nums[a] 加上后面3个最大的数 < target，nums[a] 必然不能符合条件，但是nums[a+1]有可能
            if (aNum + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;
            for (int b = a + 1; b < n - 2; b++) {
                // 注意，需要判断 b > a + 1
                if (b > a + 1 && nums[b] == nums[b - 1]) continue;
                int bNum = nums[b];
                if (aNum + bNum + nums[b + 1] + nums[b + 2] > target) break;
                if (aNum + bNum + nums[n - 1] + nums[n - 2] < target) continue;

                int c = b + 1, d = n - 1;
                while (c < d) {
                    long sum = aNum + bNum + nums[c] + nums[d];
                    if (sum < target) {
                        c++;
                    } else if (sum > target) {
                        d--;
                    } else {
                        lists.add(Arrays.asList((int) aNum, bNum, nums[c], nums[d]));
                        while (c < d && nums[c] == nums[c + 1]) c++;
                        while (c < d && nums[d] == nums[d - 1]) d--;
                        c++;
                    }
                }
            }
        }

        return lists;
    }

}
